﻿#include<iostream>
#include<string>
using namespace std;

//命名空间的使用
//1.使用using使用命名空间成员之一
//using jiantao::n;
//2.using namespace jiantao
//全部展开，失去封装的效果
//namespace jiantao
//{
//	int n = 10;
//	//可以嵌套使用
//	namespace id
//	{
//		int b = 2;
//	}
//}
//
//int main()
//{
//	cout << jiantao::n << endl;
//	cout << jiantao::id::b << endl;
//	cout << n << endl;
//
//	return 0;
//}

//缺省参数
//void fun()
//{
//	cout << "fun()" << endl;
//}
//
//void fun(int a ,int b=10,int c=20)
//{
//	cout << a << endl;
//	cout << b << endl;
//	cout << c << endl;
//
//}
//int main()
//{
//	fun(1);
//	fun(1,2);
//}


//函数重载
//int add(int a, int b)
//{
//	return a + b;
//}
//double add(double a, double b)
//{
//	return a + b;
//}
//int main()
//{
//	add(1, 2);
//	add(1.1, 1.2);
//	cout << "dd";
//	return 0;
//}

// C++项目
// 告诉C++编译器，extern "C"{}里面的函数是C编译器编译的，链接的时候用C的函数名规则去找，就可以链接上
//extern "C"
//{
//#include "../../DS/DS/Stack.h"
//}
//
//bool isValid(char * s){
//	ST st;
//	StackInit(&st);
//	while (*s)
//	{
//		if (*s == '('
//			|| *s == '{'
//			|| *s == '[')
//		{
//			StackPush(&st, *s);
//			++s;
//		}
//		else
//		{
//			// 遇到右括号了，但是栈里面没有数据，说明
//			// 前面没有左括号，不匹配，返回false
//			if (StackEmpty(&st))
//			{
//				StackDestroy(&st);
//				return false;
//			}
//
//			STDataType top = StackTop(&st);
//			StackPop(&st);
//			if ((*s == '}' && top != '{')
//				|| (*s == ']' && top != '[')
//				|| (*s == ')' && top != '('))
//			{
//				StackDestroy(&st);
//				return false;
//			}
//			else
//			{
//				++s;
//			}
//		}
//	}
//
//	// 如果栈不是空，说有栈中还有左括号未出
//	// 没有匹配，返回是false
//	bool ret = StackEmpty(&st);
//	StackDestroy(&st);
//	return ret;
//}
//
//int main()
//{
//	cout << isValid("{[]}") << endl;
//	cout << isValid("([)]") << endl;
//	
//
//	return 0;
//}



//int main()
//{
//	const int a = 10;
//	auto b = a;
//	cout << typeid(b).name() << endl;
//
//	int x = 1;
//	auto a = x; //int
//	auto&b = x; //int
//	auto*c = &x;//int *
//
//
//	return 0;
//}

//int main()
//{
//	int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
//	for (auto e: arr)
//	{
//		cout <<" "<< e;
//	}
//	cout << endl;
//
//	//每个值加1
//	for (auto&e : arr)
//	{
//		e++;
//	}
//	cout << endl;
//	for (auto e : arr)
//	{
//		cout << " " << e;
//	}
//	cout << endl;
//}

//void f(int)
//{
//	cout << "f(int)" << endl;
//}
//void f(int *)
//{
//	cout << "f(int *)" << endl;
//}
//int main()
//{
//	f(NULL);//调用了f(int),本意是调用f(int*)
//	f(nullptr);//调用f(int *)
//}

//class Student
//{
//private:
//	//成员变量
//	char _name[10];
//	int _age;
//public:
//	//成员方法
//	void Init(const char*name,int age)
//	{
//		strcpy_s(_name, name);
//		_age = age;
//	}
//	void Print()
//	{
//		cout << _name << endl;
//		cout << _age << endl;
//
//	}
//};
//
//int main()
//{
//	Student s1;
//	s1.Init("小米",1);
//	s1.Print();
//	return 0;
//}


//class A1
//{
//public:
//	void f()
//	{}
//private:
//	int _age;
//	int _id;
//};
//
//class A2
//{
//public:
//	void f()
//	{}
//};
//
//class A3
//{
//
//};
//
//int main()
//{
//	A1 a;
//	cout << sizeof(a) << endl;//4
//	A2 b;
//	cout << sizeof(b) << endl;//1
//	A3 c;
//	cout << sizeof(c) << endl;//1




////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//class A
//{
//public:
//	void Show()
//	{
//		cout << "Show()" << endl;
//	}
//
//	void PrintA()
//	{
//		cout << _a << endl;
//	}
//
//private:
//	int _a;
//};
//
//int main()
//{
//	A* p = nullptr;
//	p->Show();
//	p->PrintA();
//}
//
//




//class Date
//{
//public:
//	void Init(int year,int month,int day)
//	{
//		_year = year;
//		_month = month;
//		_day = day;
//	}
//	void Print()
//	{
//		cout << _year <<" "<<_month<<" "<<_day<< endl;		
//	}
//private:
//	int _year;
//	int _month;
//	int _day;
//};
//
//int main()
//{
//	Date d1,d2;
//	d1.Init(2023,5,19);
//	d2.Init(2023,5,20);
//	d1.Print();
//	d2.Print();
//
//	return 0;
//}


////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//析构和构造函数
//class Date
//{
//public:
//	//显示定义构造函数
//	Date(int year = 0, int month = 1, int day = 1)
//	{
//		_year = year;
//		_month = month;
//		_day = day;
//	}
//	
//	//拷贝构造
//	Date(const Date& d)
//	{
//		_year = d._year;
//		_month = d._month;
//		_day = d._day;
//
//	}
//
//	//赋值运算符重载
//	Date& operator=(const Date& d)
//	{
//		if (this != &d)//地址的比较
//		{
//			_year = d._year;
//			_month = d._month;
//			_day = d._day;
//		}
//
//		return *this;
//	}
//
//private:
//	int _year;
//	int _month;
//	int _day;
//};
//
//
//class Stack
//{
//public:
//	Stack(int capacity = 4)
//	{
//		_a = (int *)malloc(sizeof(int)*capacity);
//		if (_a = nullptr)
//		{
//			cout << "malloc fail" << endl;
//		}
//		_capacity = capacity;
//		_top = 0;
//	}
//
//	~Stack()
//	{
//		free(_a);
//		_a = nullptr;
//		_capacity = _top = 0;
//	
//	}
//private:
//	int *_a;
//	size_t _capacity;
//	size_t _top;
//};
//
//
//int main()
//{
//	Date d1(2023,1,1);
//	Date d2(d1);
//	Stack s1;
//	Date d3;
//	d3 = d1;
//	return 0;
//}
//







/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//日期类
//
//#include"Date.h"
//void test1()
//{
//	Date d1(2000,3,12);
//	d1.Print();
//	Date d2(2022, 2, 29);
//	Date d3(d2);
//	int ret1 = (d1 < d2);
//	cout << ret1 << endl;
//	int ret2 = (d2 == d3);
//	cout << ret2 << endl;
//}
//
//void test2()
//{
//	Date d1(2022, 1, 15);
//	d1 += 100;
//	d1.Print();
//	Date d2(2022, 1, 15);
//	Date d3(d2 + 100);
//	d2.Print();
//	d3.Print();
//}
//
//
//void test3()
//{
//	Date d1(2022, 1, 15);
//	d1.Print();
//	++d1; //d1.operator++(&d1);
//	d1.Print();
//
//	Date d2(2022, 2, 15);
//	d2.Print();
//	d2++;
//	d2.Print();
//}
//
//
//void test4()
//{
//	Date d1(2022, 1, 13);
//	Date d2;
//	d2 = d1;//d2.operator=(d1);
//	d2.Print();
//}
//
//
//
//void  test5()
//{
//	Date d1(2023, 5, 21);
//	Date d2(d1 - 1500); //2019年4月12 星期五
//	d2.Print();
//}
//
//void test6()
//{
//	Date d1(2023, 4, 21);
//	Date d2(2023, 5, 19);
//	cout << (d1 - d2) << endl;
//}
//
//
//void test7()
//{
//	Date d1(2023, 5, 30);
//	d1.PrintWeekDay();
//
//	Date d2(2023, 6, 2);
//	cout <<d2<<d1;
//}
//
//
//
//int main()
//{
//	
//	test7();
//}




///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//初始化列表
//class Date1
//{
//public:
//	 Date1(int year = 1, int month = 1, int day = 1)
//   explicit Date1(int year = 1, int month = 1, int day = 1) 
//		:_year(year)
//		, _month(month)
//		, _day(day)
//	{}
//private:
//	int _year;
//	int _month;
//	int _day;
//};
//int main()
//{
//	Date1 d1;
//	Date1 d2(2022, 1, 1);
//	d2 = 2023;
//	return 0;
//}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//一个题
//class A
//{
//public:
//	A(int a)
//		:_a1(a)
//		, _a2(_a1)
//	{}
//
//	void Print() {
//		cout << _a1 << " " << _a2 << endl;
//	}
//private:
//	int _a2;
//	int _a1;
//};
//
//int main() {
//	A aa(1);
//	aa.Print();
//}



//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//static
//class A
//{
//public:
//	A(int a = 1)
//		:_a(a)
//	{
//		_scount++;
//	}
//	A(const A& a)
//		:_a(a._a)
//	{
//		_scount++;
//	}
//	void Getcout()
//	{
//		cout << _scount;
//	}
//private:
//	int _a;
//	static int _scount;
//};
//
//int A::_scount = 0;
//
//int main()
//{
//	A a;
//	a.Getcout();
//	return 0;
//}

//////////////////////////////////////////////////////////////////////////////////
//C++11
//class A
//{
//public:
//	A()	
//	{}
//private:
//	int _year = 2022;
//};
//
//int main()
//{
//	A a;
//}


///////////////////////////////////////////////////////////////////////////////////////////////////////
//友元

//class A
//{
//	friend class B; //在a里说b是a的朋友，就可以在b中调用a的私有成员变量
//public:
//	A(int a = 1, int b = 1, int c=1)
//		:_a(a)
//		, _b(b)
//		, _c(c)
//	{}
//private:
//	int _a;
//	int _b;
//	int _c;
//};
//
//class B
//{
//	
//public:
//	B(int d = 2, int e = 2, int f = 2)
//		:_d(d)
//		, _e(e)
//		, _f(f)
//	{}
//	void InitA(int a=3,int b=3,int c=3)
//	{
//		_a._a = a;
//		_a._b = b;
//		_a._c = c;
//	}
//private:
//	int _d;
//	int _e;
//	int _f;
//	A  _a;
//};
//
//int main()
//{
//	B b;
//	b.InitA();
//}



/////////////////////////////////////////////////////////////////////////////////
//内部类
//class A
//{
//	
//public:
//	A(int a = 1, int b = 1, int c=1)
//		:_a(a)
//		, _b(b)
//		, _c(c)
//	{}
//	class B
//	{
//		
//	public:
//		B(int d = 2, int e = 2, int f = 2)
//			:_d(d)
//			, _e(e)
//			, _f(f)
//		{}
//		//像友元一样访问A的私有成员
//		void PrintA(const A& a)
//		{
//			cout << a._a << a._b << a._c << endl;
//		}
//		
//	private:
//		int _d;
//		int _e;
//		int _f;
//	};
//private:
//	int _a;
//	int _b;
//	int _c;
//};
//
//int main()
//{
//	A::B b;
//	b.PrintA(A());
//	return 0;
//}


////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//一个题
//class Sum
//{
//public:
//	Sum()
//	{
//		_ret += _i;
//		_i++;
//	}
//	static int Getcount()
//	{
//		return _ret;
//	}
//private:
//	static int _i;
//	static int _ret;
//};
//
//int Sum::_i = 1;
//int Sum::_ret = 0;
//
//class Solution {
//public:
//	int Sum_Solution(int n) {
//		//Sum a[n];//变长数组
//		Sum*p = new Sum[n];
//		return Sum::Getcount();
//	}
//};
//
//int main()
//{
//	Solution a;
//	a.Sum_Solution(4);
//}



//////////////////////////////////////////////////////////////////////
//根据输入的日期，计算是这一年的第几天。
//
//int GetMonthday(int year, int month) 
//{
//
//	int monthday[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31,30,31 };
//	int day = monthday[month];
//	if ((month == 2) && ((year % 100 != 0) && (year % 4 == 0) ||
//		(year % 400 == 0))) {
//		day += 1;
//	}
//	return day;
//}

//int main()
//{
//	int year, month, day, ret = 0;
//	while (cin >> year >> month >> day)
//	{
//		for (int i = 0; i<month; i++)
//		{
//			ret += GetMonthday(year, i);
//
//		} 
//		cout << ret + day;
//	}
//}



/////////////////////////////////////////////////////////////////////////////
//有两个日期，求两个日期之间的天数，如果两个日期是连续的我们规定他们之间的天数为两天

//bool Ismax(int year1, int month1, int day1, int year2, int month2, int day2) {
//	if (year1 > year2)
//		return true;
//	else if (year1 == year2) {
//		if (month1 > month2)
//			return true;
//		else if (month1 == month2) {
//			if (day1 > day2)
//				return true;
//		}
//	}
//	return false;
//}
//
//void Swap(int& a, int& b)
//{
//	int tmp = a;
//	a = b;
//	b = tmp;
//}
//
//int GetMonthday(int year, int month) {
//
//	int monthday[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
//	int day = monthday[month];
//	if ((month == 2) && ((year % 100 != 0) && (year % 4 == 0) ||
//		(year % 400 == 0))) {
//		day += 1;
//	}
//	return day;
//}
//
//int main() {
//	int year1, month1, day1;
//	int year2, month2, day2;
//	int count = 1;
//	scanf("%4d%2d%2d", &year1, &month1, &day1);
//	scanf("%4d%2d%2d", &year2, &month2, &day2);
//
//	//小的换过来
//	if (!(Ismax(year1, month1, day1, year2, month2, day2)))
//	{
//		Swap(year1, year2);
//		Swap(month1, month2);
//		Swap(day1, day2);
//	}
//
//	//把小的+到和大的相等
//	while (year1 != year2 || month1 != month2 || day1 != day2)
//	{
//		count++;
//		day2++;
//		//加到day超过正常日期就近月
//		if (day2>GetMonthday(year2, month2))
//		{
//			day2 = 1;
//			month2++;
//			if (month2 == 13)
//			{
//				month2 = 1;
//				year2++;
//			}
//		}
//	}
//
//	cout << count << endl;
//
//}
//
//






/////////////////////////////////////////////////////////////////////////////////////////////////////////
//设计一个程序能计算一个日期加上若干天后是什么日期
//int GetMonthday(int year, int month) {
//
//	int monthday[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30 ,31};
//	int day = monthday[month];
//	if ((month == 2) && ((year % 100 != 0) && (year % 4 == 0) ||
//		(year % 400 == 0))) {
//		day += 1;
//	}
//	return day;
//}
//
//int main()
//{
//	int m, year, month, day, add;
//	cin >> m;
//	while (m) {
//		cin >> year >> month >> day >> add;
//		int add_day = add + day;
//		while (add_day>GetMonthday(year, month))
//		{
//			add_day -= GetMonthday(year, month);
//			month++;
//			if (month == 13)
//			{
//				year++;
//				month = 1;
//			}
//		}
//		printf("%d-%02d-%d\n", year, month, add_day);
//		m--;
//	}
//}


//////////////////////////////////////////////////////////////////////
//内存管理
//class Test
//{
//public:
//	Test()
//		:_a(0)
//	{
//		cout << "Test()" << endl;
//	}
//	
//	~Test()
//	{
//		cout << "~Test()" << endl;
//	}
//private:
//	int _a;
//};
//
//
//int main()
//{
//	//c 动态申请一个int类型的空间
//	int *p = (int *)malloc(sizeof(int));
//	free(p);
//
//	//c++动态申请一个int类型的空间
//	int *p1 = new int;
//	delete p1;
//
//	//动态申请一个int类型的空间并初始化
//	int *p2 = new int(2);
//	delete p2;
//
//	//动态申请5个int类型的空间
//	int *p3 = new int[5];
//	delete[] p3;
//
//
//	Test*p4 = new Test;
//	delete p4;
//
//	Test*p5 = new Test[10];
//	delete[] p5;
//
//
//
//	//定位new
//	Test *p6 = (Test*)malloc(sizeof(Test));
//	new(p6)Test; //如果构造类型有参数需要传参
//
//	return 0;
//}

/////////////////////////////////////////////////////////////////////////////////////
//给出年分m和一年中的第n天，算出第n天是几月几号
//int GetMonthday(int year, int month) {
//
//	int monthday[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
//	int day = monthday[month];
//	if ((month == 2) && ((year % 100 != 0) && (year % 4 == 0) ||
//		(year % 400 == 0))) {
//		day += 1;
//	}
//	return day;
//}
//int main() {
//	int year, month = 1, day;
//	while (cin >> year >> day)
//	{
//		while (day>GetMonthday(year, month))
//		{
//			day -= GetMonthday(year, month);
//			month++;
//		}
//		printf("%4d-%02d-%02d", year, month, day);
//
//	}
//
//}


//int main()
//{
//	char *p = new char[100];
//	delete p;
//	return 0;
//}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//int main(int argc, char *argv[])
//{
//	string a = "hello world";
//	string b = a;
//	if (a.c_str() == b.c_str()){
//	cout << "true" << endl;
//	}
//	else cout << "false" << endl;
//
//	string c = b;
//	c = "";
//	if (a.c_str() == b.c_str()	{
//		cout << "true" << endl;
//	}
//	else cout << "false" << endl;
//
//	a = "";
//	if (a.c_str() == b.c_str()){
//		cout << "true" << endl;
//	}
//
//	else cout << "false" << endl;
//	return 0;
//
//}

///////////////////////////////////////////////////////////////////////////////////////////////
//int main(int argc, char *argv[])
//{
//	string strText = "How are you?";
//	string strSeparator = " ";
//	string strResult;
//	int size_pos = 0;
//	int size_prev_pos = 0;
//	while ((size_pos = strText.find_first_of(strSeparator, size_pos)) != string::npos)
//	{
//		strResult = strText.substr(size_prev_pos, size_pos - size_prev_pos);
//		cout << strResult << " ";
//		size_prev_pos = ++size_pos;
//	}
//
//	if (size_prev_pos != strText.size())
//	{
//		strResult = strText.substr(size_prev_pos, size_pos - size_prev_pos);
//		cout << strResult << " ";
//	}
//	cout << endl;
//	return 0;
//}
//


/////////////////////////////////////////////////////////////////////////////////////////////////////////////
//字符相加  每个转化为数字再相加
//int main()
//{
//	string num1("123");
//	string num2("11");
//	  string add;
//        int size1=num1.size()-1;
//        int size2=num2.size()-1;    
//        int carry=0;
//        while( size1>=0 || size2>=0)
//        {
//            int x=0;
//           if(size1>=0)
//            {
//                x=num1[size1]-'0';
//                --size1;
//            }
//            int y=0;
//            if(size2>=0)
//            {
//                y=num2[size2]-'0';
//                --size2;
//            }
//           int add_sum=x+y+carry;
//            if(add_sum>9)
//            {
//                carry=1;
//                add_sum-=10;
//            }
//            else{
//                carry=0;
//            }
//            add+=add_sum+'0';     
//        }
//        if(carry==1)
//        {
//            add+='1';
//        }
//        reverse(add.begin(),add.end());
//		cout << add.c_str() << endl;
//}


//////////////////////////////////////////////////////////////////////////////////////////////
//把字符串转化为整数
//int main()
//{
//	class Solution {
//	public:
//		int StrToInt(string str) {
//			int flag = 1;
//			int i = 0;
//			if (str[0] == '-' || str[0] == '+')
//			{
//				if (str[0] == '-')
//				{
//					flag = -1;
//					i++;
//				}
//				if (str[0] == '+')
//				{
//					flag = 1;
//					i++;
//				}
//			}
//			int sum = 0;
//			for (; i<str.size(); i++)
//			{
//				if (str[i]<'0' || str[i]>'9')
//				{
//					return 0;
//				}
//				sum = sum * 10 + str[i] - '0';
//			}
//			return flag*sum;
//
//		}
//	};
//}